function [x,z]=simplex( A,b,c );
%z=min cx
%Ax<=b
%x>=0

%get the initial B, we set it as B,N
[row,cloumn]=size(A);
temp=1:cloumn;
B_idx=temp>cloumn-row;
N_idx=(1-B_idx)>0;

x=zeros(cloumn,1);
z=0;
b1=b;
c1=c;
flag=0;
A1=A;
B_order=[cloumn-row+1:cloumn];

while(1)
idx_in_temp=find_base_in(c1(N_idx));
if idx_in_temp<0
    flag=1;%done
    break;
else
    if idx_in_temp==0
        flag=0;%done many solution
        break;
    end
end
idx_in_1=find(N_idx);
idx_in=idx_in_1(idx_in_temp);
idx_out_temp=find_base_out(b1,A1(:,idx_in));
if idx_out_temp<0
    flag=-1;%infty
    break;
end
idx_out=B_order(idx_out_temp);
B_order(idx_out_temp)=idx_in;

[B_idx(idx_in) B_idx(idx_out)]=deal(B_idx(idx_out),B_idx(idx_in));
N_idx=(1-B_idx)>0;
B_o=A1(:,B_order);
A1=B_o\A1;
b1=B_o\b1;

z=z-c1(idx_in).*b1(idx_out_temp);
c1 = c1-c1(idx_in).*transpose(A1(idx_out_temp,:));

end
if flag==1
    display('get the optimal solution');
    x=zeros(cloumn,1);
    x(B_order)=b1;
else
    if flag==-1
        display('opt is infty');
        z=inf;
    else
        display('many solution');
    end
end

end

function [idx]=find_base_in(C_N);
    if isempty(C_N)
        idx=-1;
        return;
    end
    [min_value,idx_1]=min(C_N);
    if min_value<0
        idx=idx_1(1);
    else if min_value==0
            idx=0;
        else
            idx=-1;
        end
    end
    idx=int8(idx);
end

function [idx]=find_base_out(b1,A_i);
    A_n=A_i<0;
    if sum(A_n)
        idx=-1;%infty
        return;
    end
    A_i(A_i==0)=A_i(A_i==0)+eps;
    [min_value,idx_1]=min(b1./A_i);
    idx=idx_1(1);
    idx=uint8(idx);
end